Type Inference is Brian Hackett's type inference engine for JavaScript. It is a whole-program, hybrid static and dynamic analysis that attempts to find the set of possible types for stack slots, arguments, and local variables.

Some information can only be deduced at run-time, for example, the effects of an eval or integer overflow. If assumptions about type information are broken, the analysis is re-run on anything depending on that information. This can cause methods to be recompiled, even replacing currently running methods on the stack.

Bug 608741 is the meta bug for integrating into JM.

The project repository is http://hg.mozilla.org/projects/jaegermonkey.

Planning

Firefox 5

In order to ship with Firefox 5, tentatively we must land by the end of March 2011. Minimally, this is what we should aim for:

• Type inference engine integrated into JägerMonkey, with cross-branch register allocation for both GP and FPU registers.
• With TI enabled, JägerMonkey is epsilon faster than JägerMonkey without type inference.
• JägerMonkey and TraceMonkey, with TI disabled, are no slower than pre-TI.
• Browser works and tinderbox is green.

Completed Work

The inference engine is working in the shell. GP and FPU register allocation works, as does registers across control-flow edges.

Some Numbers

Some initial numbers from tests where we know type inference does really well.

Next Steps

• JS peers need to read, understand, and audit the jaegermonkey branch.
• bug 619425 Find, understand, and fix benchmarks which have regressed.
• bug 613221 Type inference data structures need memory management.
• bug 619433 Integrate TI+JM into the browser.
• bug 619415 Fuzz bugs and the like.
• Possible retuning of the trace profiler.

Technology

Implementation

Type inference has a somewhat invasive integration into the engine as a whole, but is designed to integrate with JaegerMonkey with as few changes to the compiler as possible. It uses the existing FrameState API to act as an oracle for JaegerMonkey's register allocator and type information queries.

Type sets for stack slots are queried based on a script, program counter, and stack/local/argument index. Type information for object properties is stored in each JSObject, and contains the set of properties and types of those properties that can be visible from that object at any point in time. For each js::Shape, there is exactly one type object; but a type object can be shared across multiple shapes.

For both, the type information forms the constraint graph necessary for propagating new additions to type sets, causing recompilation.

This propagation is critical for correctness in code that depends on type inference information. Thus the interpreter and VM helpers must carefully place type checks where necessary, triggering a re-analysis if a new type is added to a type set.

The register allocator uses liveness information computed in a backwards pass. During loop compilation the compiler decides which values should be kept in registers across the backwards edge. That means the full set of loop-carried registers is not unknown until the bottom of the loop.

To account for this, there are two JM modifications:

• As loop-carried registers are allocated, previously generated out-of-line paths need to be patched to restore the register.
• Code generation of the loop entry is deferred until all loop-carried registers are known.

Future optimizations

Post Firefox 5, we're looking to:

• Add loop invariant code motion, hoisting guards, and possibly even array dslots loads.
• Common sub-expression elimination within basic blocks.
• Function inlining.
• Combine js::Shape, type objects, and JSObject::prototype.
• Use object type information to eliminate shape guards.